In a computer system, a compiler is utilized to convert a software program in a programming language into machine language. A processor then may execute the machine language to perform the operations designated by the software program. However, inefficiencies arise when using compilers due to an overlap of executable instructions within the programming language and subsequent redundancies in the machine language program.
As part of the compiler process, compilers attempt to determine the equivalence of expressions. If two expressions are equivalent, then the second computation can be removed from the program. There are existing techniques that determine equivalence using hash-based value numbers. These techniques are limited because existing techniques only identify equivalence of scalar expressions and do not find equivalence of vectors.
Value numbering is a well known compiler optimization technique. Each unique value computed in a program is assigned a number called a value number. Earlier techniques applied value numbering to each basic block individually; this is termed “local value numbering”. For each instruction in the block, value numbering hashes the operation code and the value numbers of the source operands to obtain a unique number representing the output of the instructions. For example, if the instruction is the addition of two elements, a first, element and a second element, the value number is determined by the hash of the combination of the addition command with the first element and the second element.
Once a value is hashed, the resultant hash value is compared with a hash table. If the instruction is redundant, the hash value will already exist in the hash table. When the hash value already exists in the hash table, the re-computation can be replaced with a reference to the previously computed value. Any operator with known constant arguments is evaluated and the resulting value is used to replace any subsequent references.
Further techniques provide for commutativity, algebraic identities, and extending value numbering beyond the local domain. With this latter technique, termed “global value numbering”, a stack of hash tables is used such that the value numbering may be performed over multiple blocks of instructions.
There are numerous approaches to hash-based value numbering. These different approaches provide variant techniques on how the instructions are processed, the number of hash tables, when the hash tables are re-initialized, exactly how the value numbers are assigned when an operand is first seen and when value numbering is applied.
None of the current approaches to hash-based value numbering apply to machines with instructions that generate more than one result, and which have registers which can store more than one result. The latter are termed “superword registers”. For ease of description, we will work with superword registers that can store four 32-bit values; each storage area of the superword register is a “component”; we label the four components “x”, “y”, “z”, “w”. Note though that the method we describe is equally applicable to any combination of superword registers of any size (where “size” is the number of components) and machines with instructions that return any number of results.
One current approach to overcome this limitation of hash-based value numbering is to treat the register result as a single value. This approach ignores the individual components which thereby leads to inefficient code because a result for a first component does not necessarily correspond to a result for any or all of the other components.
A proposed solution to overcome the above-noted limitation of existing hash-based value numbering techniques as applied to superword registers is for the compiler to split each instruction that operates superword instructions into a set of n scalar operations, where n is the number of components of the superword register. This approach is problematic because the number of register allocations needed for the hash-based valued numbering is thereby greatly increased. Also, this approach has a large adverse affect on the compilation time because the number of instructions to be compiled has just been increased by a factor of n.
In a single instruction multiple data (SIMD) processing environment, there are advantages to using a superword register, wherein a superword register includes a hardware resource that can hold a small, but more than one, number of words of data. In one exemplary orientation, the superword register can hold up to 128 bits divided into four floating point elements. In the SIMI processing environment, instructions that operate on superword registers operate in parallel on all elements and therefore are capable of achieving very high performance provided that more than one element contains data.
Application of value numbering can determine which instructions are duplicates However, as compilers using superword registers fail to account for the multiple components, such compilers do not perform value numbering consistent with the benefits of the superword register and therefore fail to enhance on the added benefit and improved processing ability of using the superword register in the SIMD processing environment.
Instructions operating on a superword register can also support specialized features which further complicate the picture. A first such feature is a swizzling operation, wherein the instruction allows for the re-ordering of the superword values, more specifically the components having associated values. A second possible feature is a write mask which indicates which components an instruction writes in the superword register and which components the superword register utilize previous values.
Current hash based value numbering techniques cannot properly and efficiently process instructions associated with superword registers. Therefore, there exists a need for a hash based value numbering approach optimizing compiler operations for instructions associated with superword registers.